//
//Copyright GX. Yuan
//
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
//   http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.

/**
 * @file net.go
 * @brief Leetcode practice
 * @details 下一个排列
 * @author GX. Yuan  any question please send mail to yuanguanxu@qq.com
 * @date 2021-6-28
 * @version V1.0
 * @attention 硬件平台: windows 10 家庭版
 * SDK版本：Go 1.16.5
 * IDE版本：GoLand 2020.2.3
 */
package main

import (
	"fmt"
	"sort"
)

func nextPermutation(nums []int) {
	site := 0
	for j := len(nums) - 1; j > 0; j-- {
		if nums[j] > nums[j-1] {
			site = j // site 表示需要交换的那个位置
			break
		}
	}
	if site == 0 {
		sort.Ints(nums)
	} else {
		sort.Ints(nums[site:])
		for i := site; i < len(nums); i++ {
			if nums[site-1] < nums[i] {
				tempnums := nums[i]
				nums[i] = nums[site-1]
				nums[site-1] = tempnums
				break
			}
		}
	}
	fmt.Println(nums)
}
func main() {
	nums := []int{2,3,1}
	nextPermutation(nums)
}

// 思路
// 从后向前，检查 到 后一个数，大于前一个数；如果前一个数，一直是大于的话，那么就是最大的数；
// 交换后，将后面的数进行一个排序。
// 如果递归到0 ，说明整个数是最大的。那么，将整个数组排序：颠倒。

// 上面的思路是不正确

// 前一个数，替换为，后面的中比他稍微大的那个数;
// 实现方法是：
// 先是将后面的内容进行排序；然后找到比这个数大的数，交互即可;
